#include "headfiles.h"

static int strCmp(const char *str, int loc1, int loc2) {
    const char *str1 = &str[loc1];
    const char *str2 = &str[loc2];

    size_t s1 = strlen(str1);
    size_t s2 = strlen(str2);

    size_t s = (s1 > s2) ? s1 : s2;
    size_t i;

    for (i = 0; i < s; i++) {
        if (str1[i] < str2[i]) {
            return 1;
        }
        else if (str1[i] > str2[i]) {
            return -1;
        }
    }

    if (s1 < s2) {
        return 1;
    }
    else if (s1 > s2) {
        return -1;
    }

    return 0;
}

static void quickSort(const char *str, 
                      int *array, 
                      size_t start, 
                      size_t end) {
    if (start >= end - 1) {
        return;
    }

    size_t pivot_loc = (start + end) / 2;
    int pivot = array[pivot_loc];

    array[pivot_loc] = array[start];

    int index = start;
    int l = index + 1;
    int r = end - 1;

    while (l <= r) {
        int cmp_res = strCmp(str, array[l], pivot);
        if (cmp_res == 1 ||
            cmp_res == 0) {
            array[index] = array[l];
            index++;
            l++;
        }
        else {
            int tmp = array[l];
            array[l] = array[r];
            array[r] = tmp;
            r--;
        }
    }

    array[index] = pivot;

    quickSort(str, array, start, index);
    quickSort(str, array, index + 1, end);

    return;
}

bool createSuffixArray(const char *str, size_t n, int *array) {
    if (str == NULL ||
        n <= 0 ||
        array == NULL) {
        return false;
    }

    size_t i;
    for (i = 0; i < n; i++) {
        array[i] = i;
    }

    quickSort(str, array, 0, n);

    return true;
}


